Compilers, particularly optimizing compilers, facilitate efficient communication between the user/programmer and the target central processing unit (CPU). The function of a compiler is to convert code written in a high level programming language containing instructions into machine readable form, allowing those instructions to be carried out efficiently by a target CPU. Ideally, the higher level language code and the compiled, machine readable code are directed to the same set of instructions, with the machine readable code being an efficient (i.e., optimized) rendition thereof.
Optimization techniques used by prior art compilers include a register allocation step. Target CPUs have a limited number of physical registers. The number of physical registers is generally small, and only one value may occupy a physical register a time. Variables defined and utilized in program code are allocated between these physical registers and CPU memory by a phase in a compiler. Register allocation is therefore a type of resource management that may be used to enhance the efficiency of target CPU functioning. Such enhancement occurs when the most heavily accessed variables of the code are placed in physical registers.
The input variables, output variables and other variables used in certain types of operations are required by certain target CPUs to be located in physical registers. For example, a load/store CPU design requires that mathematical operations, for example, be conducted in this manner, with only loads and stores proceeding directly from/to memory.
A mathematical expression to be carried out by a load/store target CPU might be represented as follows: EQU C=A+B
In order for a target CPU to carry out this operation, variables A and B would have to reside in different physical register locations at the same time. Two physical registers would therefore have to be simultaneously available to accommodate this operation. If only one register is available at the time that this operation is to be carried out, a variable resident in a second register must be "spilled" into memory to allow the second variable involved in the operation to be allocated to that register. The choice of the particular variable to spill, when a spill is required, is an important one with respect to target CPU efficiency in carrying out code instructions.
One method of allocating registers is disclosed in U.S. Pat. No. 4,571,678 issued to Chaitin, entitled "Register Allocation and Spilling via Graph Coloring." In this approach, techniques used in graph coloring are applied to the register allocation problem, with certain modifications that allow a global spill analysis to be conducted. To accomplish physical register allocation, each variable (or set of coalesced variables as described below) is represented as a node in an interference graph. In addition, each physical register is associated with a different color.
Variables that are "live" at the same time (e.g., variables A and B in the mathematical operation set forth above) are designated as conflicting and cannot occupy the same physical register. Nodes representing conflicting variables are connected with an "edge" in an interference graph, thereby graphically indicating that the conflicting variables represented by the connected nodes cannot reside in the same physical register. As a result, the register allocation problem becomes one of coloring the interference graph such that conflicting nodes receive a different color. This goal is relatively simple to achieve when no variable has a number of conflicts greater than or equal to the number of physical registers.
When one or more variables have a number of conflicts exceeding the number of physical registers available to the target CPU, a decision must be made as to which variables will be placed in registers and which will be "spilled" into memory. According to the Chaitin patent, processes using graph coloring prior to that patent abandoned the graph coloring technique at the spill decision stage in favor of other ad hoc methodologies.
Chaitin, in U.S. Pat. No. 4,571,678, extended the application of graph coloring principles to global spill analysis. In this prior art process, an interference graph encompassing the whole of the program code under analysis is generated. This complete code interference graph is constructed using a dual variable representation involving a bit matrix and adjacency vectors. For code containing N variables, an N.times.N bit matrix is constructed, with each row I/column J location within the matrix receiving a value of 1 if the nodes I and J are adjacent (i.e., represent conflicting variables). The adjacency vector for each node reflects the set of nodes that are adjacent thereto. Specifically, the length of the adjacency vector indicates the degree (i.e., number of conflicting nodes) of each node in the interference graph.
A two step methodology is used to generate the complete code interference graph to be used in the coloring register allocation process. The first step involves the use of the bit matrix to calculate the degree of each node. Adjacency vectors are allocated storage for each node, and the second step of filling in the adjacency vectors is undertaken.
Certain variables are related to each other in a manner allowing them to occupy the same physical register. For example, nodes corresponding to related variables which are the source and target of copy operations (e.g., A=B) may be coalesced, provided that the nodes do not otherwise conflict. Coalesced nodes will be assigned the same color, and the individual variables corresponding to those nodes will be assigned to the same physical register. These related variables are identified and coalesced, and a modified interference graph is constructed. At this time, the bit matrix is updated to reflect the node combinations, and the adjacency vectors of the coalesced nodes are added together.
If the interference graph, modified to reflect the coalesced variables, exhibits a number of nodes that is less than the number of physical registers available to the target CPU, straight-forward register allocation can proceed. If not, spill decisions must be made.
Register allocation proceeds as follows. All nodes along with their edges having a number of conflicts less than the number of physical registers are serially eliminated from the interference graph. This process is referred to in the prior art patent as graph reduction. In a situation involving code for which no spill decisions need be made, all of the nodes in the interference graph are eliminated in this manner. If elimination of all of the nodes occurs, the nodes are allocated colors in the reverse order of elimination.
When all of the nodes having a number of conflicts less than the number of physical registers have been removed from the interference graph, a decision must be made with respect to the next variable to eliminate. The chosen variable will be spilled to memory. Preferably, the next variable eliminated will have a cascading effect by decreasing the number of conflicts to generate additional nodes with a number of conflicts less than the number of physical registers. In this manner, a number of additional nodes may be removed from the interference graph through the use of the graph reduction methodology discussed above.
To make a spill decision in accordance with the prior art patent, a spill cost is determined for each variable (individual and coalesced) having a number of conflicts that exceeds the number of physical registers. In other words, a spill cost is determined for each node in an interference graph having a number of adjacent/connected nodes greater than the number of physical registers. This spill cost computation is based upon an estimate of the increase in program execution time resulting from the spill of that variable, which necessitates a memory reference whenever the spilled variable is required to reside in a physical register during code execution.
The prior art spill cost estimate equals the number of definition points for the variable plus the number of uses of the variable, with each definition and use weighted by an estimated execution frequency therefor. In this weighting process, all instructions are assumed to be executed in one cycle, and each instruction contained in a loop is estimated to be executed ten more times than it would be if located outside the loop. Local program code structure is not examined more specifically (e.g., with respect to interconnectedness or relative location of the structural features) in this prior art process.
The node having the smallest spill cost/number of conflicts value is selected for elimination from the interference graph. Once this variable is eliminated, the register allocation procedure continues, with an examination of each node to determine whether the number of conflicts is less than the number of physical registers.
Certain rules are employed to provide some local information to the prior art global allocation procedure. First, if a spilled parameter is used several times and no variables go dead within a basic code block, only one memory reference is necessary for that spilled variable, because it may reside in the allocated register throughout the basic block. Also, if a variable is local to a basic block (i.e., it appears nowhere else in the code), and no variable goes dead between the local variable definition and last use, elimination of that local variable cannot simplify the register allocation process. As a result, the spill cost of that local variable is set to infinity.
In addition to the decision with respect to which variables to spill, the location of the code necessary to accomplish the spill operations must be determined. The prior art patent involves insertion of spill code at each of the definition points of the variable to be spilled and a memory reference at each use point of that variable, with the exception of the basic block situation discussed above. As a result, this methodology is generally global in scope, with variables primarily allocated to physical registers or memory over the entire program.
After the spill code is inserted, an interference graph reflecting the spill decisions is constructed to insure that the entire coloring procedure can be conducted. If not, the register allocation procedure must be undertaken again, inserting additional spill code. Convergence of this iterative procedure is generally rapid and the interference graph for each iteration is smaller than that of the previous iteration.